package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何根据入栈序列判断可能的出栈序列

func main() {
	push := "12345"
	pop := "53412"
	if isPopSerial(push, pop) {
		fmt.Println(pop, "是", push, "的一个 pop 序列")
	} else {
		fmt.Println(pop, "不是", push, "的一个 pop 序列")
	}
}

func isPopSerial(push string, pop string) bool {
	pushLen := len(push)
	popLen := len(pop)

	if pushLen == 0 || popLen == 0 || pushLen != popLen {
		return false
	}

	pushIndex := 0
	popIndex := 0

	pushRune := []rune(push)
	popRune := []rune(pop)

	stack := common.NewLinkedStack()

	for pushIndex < pushLen {
		// 把 push 序列依次入栈，直到栈顶元素等于 pop 序列的第一个元素
		stack.Push(int(pushRune[pushIndex]))
		pushIndex++

		// 栈顶元素出栈，pop 序列移动到下一个元素
		for !stack.IsEmpty() && stack.Top() == int(popRune[popIndex]) {
			stack.Pop()
			popIndex++
		}
	}

	if stack.IsEmpty() && popIndex == popLen {
		return true
	}

	return false
}
